// https://leetcode.cn/problems/min-cost-climbing-stairs/

// 题干：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
//      一旦你支付此费用，即可选择向上爬一个或者两个台阶。
//      你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
//      请你计算并返回达到楼梯顶部的最低花费。

// 示例：输入：cost = [10,15,20]
//      输出：15

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        // dp[i]表示到达i位置时候，最小花费
        // 根据最近的一步来划分问题
        // dp[i]先到达i-1位置，然后支付cost[i]，走一步
        // dp[i]先到达i-2位置，然后支付cost[i]，走两步
        // dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

        int n = cost.size();
        vector<int> dp( n + 1);

        dp[0] = dp[1] = 0;
        for (int i = 2 ; i < n + 1 ; i++)
            dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);

        return dp[n];
    }
};

int main()
{
    Solution sol;
    vector<int> cost = {10,15,20};

    cout << sol.minCostClimbingStairs(cost) << endl;
    
    return 0;
}